package linkedList;

import java.util.Arrays;
import java.util.Set;
import java.util.stream.Collectors;

class ListNode{
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val){ this.val = val;}
    ListNode(int val, ListNode next){ this.val = val; this.next = next;}
}

public class LinikedListTest {
    
    static ListNode genList(int n){
    // 随机生成长度为n的链表，每个节点值在0-100之间
    ListNode head = new ListNode();
    ListNode cur = head;
    for(int i = 0; i < n; i++){
        cur.next = new ListNode((int)(Math.random() * 100));
        cur = cur.next;
    }
    return head.next;
}

    public static void main(String[] args) {

    }

    
}


class SolutionLinikedListTest{

    /*147. 对链表进行插入排序 */
    public static ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode dummy = new ListNode(0, head);
        ListNode curr = dummy;
        // curr 指向当前已经排序好的链表的最后一个节点
        // 从头出发一个指针，依次寻找插入位置
        while(curr != null && curr.next != null){
            ListNode p = dummy;
            while(p.next.val < curr.next.val && p != curr){
                p = p.next;
            }
            if(p == curr){
                curr = curr.next;
                continue;
            }
            ListNode p1 = p.next, curr1 = curr.next;
            curr.next = curr1.next;
            p.next = curr1;
            curr1.next = p1;

        }
        return dummy.next;
    }

    public static ListNode insertionSortListOptimize(ListNode head){
        if(head == null || head.next == null)
            return head;
        ListNode dummy = new ListNode(0, head);
        ListNode curr = head;
        while(curr != null && curr.next != null){
            if(curr.val <= curr.next.val){
                curr = curr.next;
            }else{
                // 暂时摘下该插入节点
                ListNode p = dummy, toInsert = curr.next;
                curr.next = curr.next.next;

                while(p.next.val < toInsert.val){
                    p = p.next;
                }
                toInsert.next = p.next;
                p.next = toInsert;
            }
        }
        return dummy.next;
    }

    /*24. 两两交换链表中的节点 
     * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
     * 链表可以奇数长度也可以偶数长度
    */
    public static ListNode swapPairs(ListNode head) {
        // 逆置链表的变体写法
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy, curr = head;
        while(curr != null && curr.next != null){ // 考虑奇偶数
            ListNode nxt = curr.next;
            curr.next = nxt.next;
            nxt.next = curr;
            prev.next=nxt;
            prev = curr;
            curr = curr.next;
        }
        return dummy.next;
    }

    /*2487. 从链表中移除节点 
     * 给你一个链表的头节点 head 。
        移除每个右侧有一个更大数值的节点。
        返回修改后链表的头节点 head 。
    */
    public static ListNode removeNodes(ListNode head) {
        head = LinkedListUtil.reverListNode(head);
        ListNode dummy = new ListNode(0, head);
        ListNode p = dummy.next;
        while(p.next != null){
            if(p.val > p.next.val)
                p.next = p.next.next;
            else
                p = p.next;
        }
        return LinkedListUtil.reverListNode(dummy.next);
    }

    /* 1669. 合并两个链表*/
    public static ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode dummy = new ListNode(0, list1);
        ListNode p = dummy;
        int index = -1;
        a -= 1;
        
        ListNode left = null;
        while(index <= b){
            if(index == a)
                left = p;
            p = p.next;
            index++;
        }
        left.next = list2;
        ListNode tail2 = list2;
        while(tail2.next!=null){
            tail2 = tail2.next;
        }
        tail2.next = p;
    
        return dummy.next;
    }

    /*82. 删除排序链表中的重复元素 II 
     * 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
    */
    public static ListNode deleteDuplicates2(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode dummy = new ListNode(0, head);
        ListNode p = dummy;
        while (p != null) {
            int val = -1;
            if(p.next != null && p.next.next != null && p.next.val == p.next.next.val){
                val = p.next.val;
                while (p.next != null && p.next.val == val) {
                    p.next = p.next.next;
                }
            } 
            else
                p = p.next;
        }
        return dummy.next;
    }

    /* 83. 删除排序链表中的重复元素
     * 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
    */
    public static ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode p = dummy.next;
        while(p != null){
            while(p.next != null && p.val == p.next.val){
                p.next = p.next.next;
            }
            p = p.next;
        }
        return dummy.next;
    }

    /*3217. 从链表中移除在数组中存在的节点
    给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后，返回修改后的链表的头节点。
  */
    public static ListNode modifiedList(int[] nums, ListNode head) {
        Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());
        ListNode dummy = new ListNode(0, head);
        ListNode p = dummy;
        while(p != null){
            if(p.next != null && set.contains(p.next.val))
                p.next = p.next.next;
            else
                p = p.next;
        }
        return dummy.next;
    }

}


class LinkedListUtil{
    /**
     * 反转一个单链表并返回新的头节点。
     * 
     * 该方法通过迭代的方式反转链表。处理了三种情况：
     * 1. 链表为空或只有一个节点，直接返回头节点。
     * 2. 链表只有两个节点，交换这两个节点的位置。
     * 3. 链表有三个或更多节点，使用三个指针（p1, p2, p3）进行迭代反转。
     * 
     * @param head 链表的头节点
     * @return 反转后的链表的新头节点
     */
    public static ListNode reverseLinkedList(ListNode head){
        if(head == null || head.next == null)
            return head;
        if(head.next.next == null){
            ListNode p = head.next;
            p.next = head;
            head.next = null;
            return p;
        }
        ListNode p1 = head, p2 = p1.next, p3 = p2.next;
        p1.next = null;
        while(p2 != null){
            p2.next = p1;
            p1 = p2;
            p2 = p3;
            if(p3 != null)
                p3 = p3.next;
        }
        return p1;
    }

    /**
     * 逆置链表代码优化
     * @param head
     * @return
     */
    public static ListNode reverListNode(ListNode head){
        ListNode prev = null, curr = head;
        while(curr != null){
            ListNode nxt = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nxt;
        }
        return prev;
    }

}
